/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        int high = len-1, low = 0, mid;   // 向下取整
        while(low <= high) {
            mid = (high + low)/2;
            if(target == nums[mid]){
                return mid;
            }
            else if(nums[mid] > target) {
                high = mid-1;
            }
            else{
                low = mid+1;
            }
        }
        // 查找失败
        return low;
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    vector<int> nums = {1,3,5,6};
    int target = 5;

    cout << solu.searchInsert(nums, target) << endl;

    return 0;
}